package com.itzmn.datastructure.newcode;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/30 21:10
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 给定一个数组，求数组排序之后，两个相邻数据的差值的最大值,要求
 *  时间复杂度为O(N)，要求不能使用非基于比较的排序算法
 *
 *  3、6、8、4、2、6
 *  2、3、4、6、6、8
 *  1   1  2  0  2
 *  差值最大值为2
 *
 *  思路：
 *   所有的基于比较的排序算法，时间复杂度都比O(N)大，
 *   使用桶的概念。有N个数，我们新建N+1个桶
 *   将N个数中的最小值，放在第一个桶，将最大值放在最后一个桶中，然后计算剩下数据
 *   应该放在哪个桶中(把最大数与最小数的差值，等分为N+1份，然后计算)，最后一定有至少一个桶是空的，我们在桶中只需要保存这个桶中的
 *   最大值和最小值，差值最大的，最基础的就是空桶两边的非空桶的差值，也有可能是其
 *   他两个桶之间的差值，差值最大的不可能在一个桶中，因为，每个桶中存放的数据是一样的，
 *   前一个桶中的最大值，一定小于后一个桶中的最小值，那么中间有一个空桶，那么这左右
 *   两个桶之间的差值一定大于桶的容量。所以最大差值不会是同一个桶，这也是为什么会有一个空桶
 *
 */
public class MaxGet {

    public static void main(String[] args) {
        new MaxGet().init();
    }

    private void init() {


    }

    public int maxget(int[] arr){

        int res = 0;
        int len = arr.length;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int i=0; i<len; i++){
            max = max > arr[len] ? max : arr[len];
            min = min < arr[len] ? min : arr[len];
        }

        if (max == min){
            return res;
        }

        // 存储对应的桶是否存放了数据
        boolean[] booleans = new boolean[len+1];
        // 存放对应桶中的最大值
        int[] maxs = new int[len+1];
        // 存放对应桶中的最小值
        int[] mins = new int[len+1];

        for (int i=0;i<len;i++){
            // 得到这个数据所在的桶
            int bucket = bucket(arr[i], len, min, max);

            // 这个桶的最大值，如果这个桶有值，比较痛的最大值和传入的值，如果没值，则最大值为传入的值
            maxs[bucket] = booleans[bucket] ? Math.max(maxs[bucket], arr[i]) : arr[i];
            mins[bucket] = booleans[bucket] ? Math.min(mins[bucket], arr[i]) : arr[i];
            booleans[bucket] = true;
        }

        int lastMax = maxs[0];
        // 计算桶之间的差值
        for (int i=1;i<=len;i++){
            if (booleans[i]){
                res = Math.max((mins[i]-lastMax) ,res );
                lastMax = maxs[i];
            }
        }
        return res;
    }

    private int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }
}
